package cn.net.scp.test.app;

import java.util.Arrays;

/**
 * @doc https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class LeetCode100 {

    public static void main(String[] args) {

        int arr[] = {2,0,2,1,1,0};
        sortColors(arr);
        System.out.println(Arrays.toString(arr));

    }

    public static void sortColors(int[] nums) {
        int n0 = 0, n1 = 0, n2 = 0;

        for (int num : nums) {
            if (num == 0) {
                nums[n2++] = 2;
                nums[n1++] = 1;
                nums[n0++] = 0;
            } else if (num == 1) {
                nums[n2++] = 2;
                nums[n1++] = 1;
            } else {
                nums[n2++] = 2;
            }
        }
        // []
    }

    public void quickSort(int[] nums, int left, int right) {
        int l = left, r = right, pivot = nums[(left + right) / 2];
        while (l < r) {
            while (nums[l] < pivot) {
                l++;
            }
            while (nums[r] > pivot) {
                r--;
            }
            if (l >= r) {
                break;
            }
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            if (nums[l] == pivot) {
                r--;
            }
            if (nums[r] == pivot) {
                l++;
            }
        }
        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            quickSort(nums, left, r);
        }
        if (right > l) {
            quickSort(nums, l, right);
        }
    }

}
